//
//  ProblemOffer32-2.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/2.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit
/*
 剑指 Offer 32 - II. 从上到下打印二叉树 II
 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

 例如:
 给定二叉树: [3,9,20,null,null,15,7],
     3
    / \
   9  20
     /  \
    15   7
 返回其层次遍历结果：
 [
   [3],
   [9,20],
   [15,7]
 ]
  
 提示：节点总数 <= 1000
 */
@objcMembers class ProblemOffer32_2: NSObject {
    func solution() {
        let root = TreeNode(3)
        root.left = TreeNode(9)
        root.right = TreeNode(20)
        root.right?.left = TreeNode(15)
        root.right?.right = TreeNode(7)
        print(levelOrder(root))
        print(levelOrderB(root))
    }

    /*
     广度搜索遍历
     */
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        if root == nil {
            return []
        }
        
        var nodeList:[TreeNode] = [root!]
        var list:[[Int]] = []
        
        var n = 0
        var node: TreeNode?
        while nodeList.isEmpty == false {
            var cList: [Int] = []
            n = nodeList.count
            while n > 0 {
                n -= 1
                node = nodeList.removeFirst()
                cList.append(node!.val)
                if node?.left != nil {
                    nodeList.append(node!.left!)
                }
                if node?.right != nil {
                    nodeList.append(node!.right!)
                }
            }
            list.append(cList)
        }
        return list
    }
    
    /*
     深度搜索遍历
     */
    var list:[[Int]] = []
    func levelOrderB(_ root: TreeNode?) -> [[Int]] {
        bfs(root, 0)
        return list
    }
    func bfs(_ root: TreeNode?, _ deep: Int) {
        if root == nil {
            return
        }
        
        if list.count == deep {
            list.append([])
        }
        list[deep].append(root!.val)
        bfs(root?.left, deep+1)
        bfs(root?.right, deep+1)
    }
}
